#include <deque>
#include <vector>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>

#include "syn.hpp"

using namespace std;

void print_item(const LR::LRItem &item) {
	cout << "{" << item.lf << "->";
	for (auto iter = item.rh.begin(); iter != item.rh.end(); ++iter) {
		cout << *iter;
	}
	cout << ", ";
	cout << item.look_ahead << "}" << endl;
}

void print_items(LR::LRItems &items) {
	for (auto item = items.begin(); item != items.end(); ++item) {
		print_item(*item);
	}
}

LR::LRItems LR::init_item() {
	LR::LRItems items;
	vector<string> rh = produce[0].second;
	rh.insert(rh.begin(), "#");							// '#'划分已读和未读
	items.insert(LR::LRItem(start, rh, "$"));
	return items;
}

void LR::get_lf_appears() {
	for (int cnt = 0; cnt < produce.size(); ++cnt) {
		if (lf_appears.find(produce[cnt].first) == lf_appears.end())
			lf_appears[produce[cnt].first] = vector<int>();
		lf_appears[produce[cnt].first].push_back(cnt);
	}
}

void LR::print_lf_appears() {
	for (int cnt = 0; cnt < symbols.size(); ++cnt) {
		cout << symbols[cnt] << " => ";
		vector<int> &lf_appear = lf_appears[symbols[cnt]];
		for (int i = 0; i < lf_appear.size(); ++i) {
			cout << lf_appear[i] << " ";
		}
		cout << endl;
	}
}

unordered_set<string> LR::first_of_list(vector<string> &sym_list) {
	unordered_set<string> res;
	for (int cnt = 0; cnt < sym_list.size(); ++cnt) {
		auto firsts = first_set[sym_list[cnt]];
		res.insert(firsts.begin(), firsts.end());
		if (!empty_map[sym_list[cnt]]) {
			return res;
		}
	}
	res.insert("$");
	return res;
}

void LR::closure(LRItems &src, LRItems &res) {
	res.clear();
	deque<LRItem> que;

	// 加入所有初始项目
	for (auto iter = src.begin(); iter != src.end(); ++iter) {
		que.push_back(*iter);
		res.insert(*iter);
	}

	while (!que.empty()) {
		LRItem lr_item = que.front();
		que.pop_front();
		int cnt;

		// 找到"#"的位置
		for (cnt = 0; cnt < lr_item.rh.size(); ++cnt) {
			if (lr_item.rh[cnt] == "#") {
				break;
			}
		}
		
		// 下一个为非终结符
		if (cnt+1 < lr_item.rh.size() && VN.find(lr_item.rh[cnt+1]) != VN.end()) {
			string new_lf = lr_item.rh[cnt+1];
			auto lf_appear = lf_appears[new_lf];
			
			// 生成后续序列
			vector<string> left;
			for (int i = cnt+2; i < lr_item.rh.size(); ++i) {
				left.push_back(lr_item.rh[i]);
			}
			left.push_back(lr_item.look_ahead); // 加入前看符号

			for (auto i = lf_appear.begin(); i != lf_appear.end(); ++i) {
				vector<string> new_rh;
				if (produce[*i].second[0] == "$") {	// 空产生式
					new_rh.push_back("#");
				} else {							// 非空产生式，插入"#"
					new_rh = produce[*i].second;
					new_rh.insert(new_rh.begin(), "#");
				}
				// 获取后续序列的First集
				auto firsts = this->first_of_list(left);

				// 将所有First集中的元素作为前看符号
				for (auto j = firsts.begin(); j != firsts.end(); ++j) {
					LRItem new_item(new_lf, new_rh, *j);
					if (res.find(new_item) == res.end()) { // 新项目未加入队列
						res.insert(new_item);
						que.push_back(new_item);
					}
				}
			}
		}
	}
}

void LR::go_to(LRItems &src, std::string sym, LRItems &res) {
	LRItems dst;
	for (auto iter = src.begin(); iter != src.end(); ++iter) { // 遍历项目集中的项目
		int cnt;
		const LRItem &item = *iter;
		vector<string> rh = item.rh;
		auto sym_pos = find(rh.begin(), rh.end(), sym);
		auto now_pos = find(rh.begin(), rh.end(), "#");

		// 要求sym正好出现在"#"的后面
		if (sym_pos != rh.end() && sym_pos == now_pos+1) {
			string tmp = *now_pos;
			*now_pos = *(now_pos+1);
			*(now_pos+1) = tmp;
			++now_pos;

			dst.insert(LRItem(item.lf, rh, item.look_ahead));
		}
	}
	this->closure(dst, res);
}

// 获取项目集的id
int get_id(deque<LR::LRItems> &que, const LR::LRItems &items) {
	int cnt;
	for (cnt = que.size()-1; cnt >= 0; --cnt) {
		if (que[cnt] == items) {
			return cnt;
		}
	}
	que.push_back(items);
	return que.size()-1;
}

// 找出所有归约项目集
LR::LRItems filter_reduce_items(LR::LRItems &src) {
	LR::LRItems res;
	for (auto iter = src.begin(); iter != src.end(); ++iter) {
		if ((*iter).rh.back() == "#") { // "#"出现在末尾
			res.insert(*iter);
		}
	}
	return res;
}

// 规约项目匹配对应的规约规则
int match_rule(vector<pair<string, vector<string>>> &produce, const LR::LRItem &item) {
	for (int cnt = 0; cnt < produce.size(); ++cnt) {
		if (item.lf != produce[cnt].first) {
			continue;
		}

		// 空产生式进行特殊判断
		if (item.rh[0] == "#" && produce[cnt].second[0] == "$") {
			return cnt;
		}

		if (item.rh.size()-1 != produce[cnt].second.size()) {
			continue;
		}
		
		int i = 0;
		for (; i < item.rh.size()-1; ++i) {
			if (item.rh[i] != produce[cnt].second[i]) {
				break;
			}
		}
		if (i == item.rh.size()-1) {
			return cnt;
		}
	}
	return -1;
}

void LR::build_predict() {
	cout << "Building LR predict table..." << endl;
	if (lf_appears.empty()) {
		this->get_lf_appears();
	}
	if (follow_set.empty()) {
		this->infer_follow_set();
	}

	LRItems init, res;

	// 清空队列
	items_que.clear();

	init = this->init_item();
	this->closure(init, res);

	items_que.push_back(res);

	int counter = 0;
	while(counter < items_que.size()) {
		predict.push_back(unordered_map<string, string>());
		init = items_que[counter++];

		// 检查规约项目
		auto reduce_items = filter_reduce_items(init);
		for (auto iter = reduce_items.begin(); iter != reduce_items.end(); ++iter) {
			if ((*iter).lf == start) {
				predict.back()["$"] = "acc";
			} else {
				int rule_id = match_rule(produce, *iter);
				if (rule_id == -1) {
					print_item(*iter);
					cerr << "Without matched rule" << endl;
					exit(-1);
				}
				predict.back()[(*iter).look_ahead] = "r"+to_string(rule_id);
			}
		}

		for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
			this->go_to(init, *iter, res);
			if (!res.empty()) {
				int id = get_id(items_que, res);

				if (VT.find(*iter) != VT.end()) {				// VT
				 	predict.back()[*iter] = "s"+to_string(id);
				} else { 										// VN
				 	predict.back()[*iter] = "g"+to_string(id);
				}
			}
		}
	}
	cout << "Finished" << endl << endl;
}

void LR::print_predict(int state) {
	cout << '\t';
	for (int cnt = 0; cnt < symbols.size(); ++cnt) {
		cout << symbols[cnt] << ":" << cnt << '\t';
	}
	auto tab = predict[state];
	cout << endl;
	for (int i = 0; i < symbols.size(); ++i) {
		if (tab.find(symbols[i]) == tab.end()) {
			cout << "{}:" << i << "\t";
		} else {
			cout << tab[symbols[i]] << ":" << i << "\t";
		}
	}
}

vector<string> LR::analyse_tokens(vector<Token> &tokens) {
	deque<int> states;
	deque<string> que; 
	vector<string> log;
	int tokens_cnt = 0, log_cnt = 0;

	states.push_back(0);
	while (true) {
		//log.push_back(to_string(log_cnt));
		log.push_back(string());
		//log.back() += "\t";
		if (que.empty()) {
			log.back() += "$";
		}else {
			log.back() += que.back();
		}
		log.back() += "#";
		if (tokens_cnt == tokens.size()) {
			log.back() += "EOF";
		} else {
			log.back() += tokens[tokens_cnt].grammar_name();
		}

		// 获取最新状态的转换表
		unordered_map<string, string> &tab = predict[states.back()];

		// 获取状态转换信息
		auto trans = tab.find("$"); // 默认取完
		if (tokens_cnt != tokens.size()) { // token尚未取完
			trans = tab.find(tokens[tokens_cnt].grammar_name());
		}

		//cout << endl << "\'" << (*trans).first << "\' " << endl;
		
		// 无法进行状态转换
		if (trans == tab.end()) {
			log.back() += "\terror";
			return log;
		}

		if ((*trans).second[0] == 's') { // 移入
			log.back() += "\tmove";
			// 获取新状态
			int new_state = atoi((*trans).second.c_str()+1);

			//cout << "Shift-in" << endl;
			//cout << states.back() << "->" << new_state << endl;

			// 跳转到新状态
			states.push_back(new_state);
			// 移入新的token
			que.push_back(tokens[tokens_cnt++].grammar_name());

		} else if ((*trans).second[0] == 'r') { // 归约
			log.back() += "\treduction";
			// 获取归约规则标号
			int rule_id = atoi((*trans).second.c_str()+1);
			// 获取归约
			vector<string> rh = produce[rule_id].second;

			//cout << "Reduction: " << produce[rule_id].first << endl;
			for (int cnt = rh.size()-1; cnt >= 0; --cnt) {
				if (rh[cnt] == "$") {
					continue;
				}
				// 状态回溯
				//cout << states.back() << "->" << states[states.size()-2] << endl;
				states.pop_back();

				if (que.back() != rh[cnt]) {
					log.back() += "\terror";
					return log;
				} 
				que.pop_back();
			}
			// 压入归约得到的非终结符
			que.push_back(produce[rule_id].first);

			auto new_tab = predict[states.back()];
			string new_trans = new_tab[que.back()];
			int new_state = atoi(new_trans.c_str()+1);
			//cout << new_trans << endl;
			//cout << states.back() << "->" << new_state << endl;
			states.push_back(new_state);
		} else if ((*trans).second == "acc") {
			log.back() += "\taccept";
			break;
		}
		++log_cnt;
	}
	return log;
}
